import math


class Inversions:
    def __init__(self, num: list[int]):
        self.origin_num = num[:]
        self.num = num[:]
        # 逆序数 O(n * logn)
        self.inversions = 0
        self._sort()

    def _sort(self):
        self._sort_by_recursion(0, len(self.num) - 1)

    def _sort_by_recursion(self, left: int, right: int):
        if left >= right:
            return

        mid = left + math.floor((right - left) / 2)
        self._sort_by_recursion(left, mid)
        self._sort_by_recursion(mid + 1, right)
        if self.num[mid] > self.num[mid + 1]:
            self._merge(left, mid, right)

    def _merge(self, left: int, mid: int, right: int):
        temp = self.num[left: right + 1]

        n = left
        i = left
        j = mid + 1

        while n <= right:
            if i > mid:
                self.num[n] = temp[j - left]
                j += 1
            elif j > right:
                self.num[n] = temp[i - left]
                i += 1
            elif temp[i - left] <= temp[j - left]:
                self.num[n] = temp[i - left]
                i += 1
            elif temp[i - left] > temp[j - left]:
                self.num[n] = temp[j - left]
                j += 1

                self.inversions += mid + 1 - i
            n += 1

    @staticmethod
    def inversions_sequence_number(s):
        # 逆序数 O(n * n)
        i_s_n = 0

        for i in range(len(s)):
            subject = s[i]
            for j in range(i, len(s)):
                if s[j] < subject:
                    i_s_n += 1
        return i_s_n


if __name__ == '__main__':
    origin_num = [8, 3, 2, 1, 2, 3, 8]
    inv = Inversions(origin_num)
    print(origin_num)
    print(f"[n * logn 复杂度] num.inv = {inv.inversions}")
    print(f"[n * n 复杂度] num.inv = {Inversions.inversions_sequence_number(origin_num)}")
